import java.util.ArrayList;
import java.util.List;

public class Solution22 {
    public List<String> generateParenthesis(int n) {
        List<String> ans=new ArrayList<>();
        StringBuilder stringBuilder=new StringBuilder();
        dfs(0,0,stringBuilder,ans,n);
        return ans;
    }

    private void dfs(int k, int res, StringBuilder stringBuilder, List<String> ans,int n) {
        if (k==n){
            int t=res;
            while (t!=0){
                stringBuilder.append(')');
                t--;
            }
            ans.add(stringBuilder.toString());
            while (t<res){
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
                t++;
            }
            return;
        }
        if (res>0){
            stringBuilder.append(')');
            dfs(k,res-1,stringBuilder,ans,n);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
        stringBuilder.append('(');
        dfs(k+1,res+1,stringBuilder,ans,n);
        stringBuilder.deleteCharAt(stringBuilder.length()-1);
    }

    public static void main(String[] args) {
        System.out.println(new Solution22().generateParenthesis(3));
    }


}
